package code;

public class Partition_day06 {
    public static ListNode partition(ListNode head, int x) {
        ListNode p=head;
        ListNode pre=head;
        while (p!= null) {
            if(p.val < x) {
                int temp=pre.val;
                pre.val=p.val;
                p.val=temp;
                pre=pre.next;
            }
            p=p.next;
        }
        return head;


    }
    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
    public static void main(String[] args) {
          ListNode head = new ListNode(3);head.next = null;
          ListNode temp1= new ListNode(5);head.next = temp1;
          ListNode temp2= new ListNode(4);temp1.next = temp2;
          ListNode temp3= new ListNode(3);temp2.next = temp3;
          ListNode temp4= new ListNode(2);temp3.next = temp4;
          ListNode temp5= new ListNode(1);temp4.next = temp5;
          head= partition(head,3);
          ListNode p=head;
          while (p != null) {
              System.out.println(p.val);
              p=p.next;
          }
    }
}
